package io.gimo.study.design_pattern.factory.abstract_factory.product;


import io.gimo.study.design_pattern.factory.abstract_factory.Sortor;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class RadixSortor implements Sortor {

	@Override
	public void sort(int[] target) {
		//找到最大数，确定要排序几趟
        int max = 0;
        for (int i = 0; i < target.length; i++) {
            if(max<target[i]){
                max = target[i];
            }
        }
        //判断位数
        int times = 0;
        while(max>0){
            max = max/10;
            times++;
        }
        //建立十个队列
        List<List<Integer>> queue = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            ArrayList<Integer> queue1 = new ArrayList<>();
            queue.add(queue1);
        }
        //进行times次分配和收集
        for (int i = 0; i < times; i++) {
            //分配
            for (int j = 0; j < target.length; j++) {
                int x = target[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
                List<Integer> queue2 = queue.get(x);
                queue2.add(target[j]);
                queue.set(x,queue2);
            }
            //收集
            int count = 0;
            for (int j = 0; j < 10; j++) {
                while(queue.get(j).size()>0){
                    List<Integer> queue3 = queue.get(j);
                    target[count] = queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
            }
        }
        System.out.println(Arrays.toString(target));
	}

}
